package leetcode.day_2021_03_22_2021_03_28;

public class LeetCode0079 {
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        for (int row=0; row<rows; row++) {
            for (int col=0; col<cols; col++) {
                if (dfs(rows, cols, row, col, board, visited, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(int rows, int cols, int row, int col, char[][] board, boolean[][] visited, String word, int pathLength) {
        if (pathLength == word.length()-1) {
            return board[row][col] == word.charAt(pathLength-1);
        }

        boolean hasPath = false;
        if(row>=0 && row<rows && col>=0 && col<cols && !visited[row][col] && board[row][col]==word.charAt(pathLength)) {
            visited[row][col] = true;
            for (int i=0; i<4; i++) {
                int newRow = DIRECTIONS[i][0] + row;
                int newCol = DIRECTIONS[i][1] + col;
                if (dfs(rows, col, newRow, newCol, board, visited, word, ++pathLength)) {
                    return true;
                }
            }
            visited[row][col] = false;
        }
        return false;
    }
}
